24. 两两交换链表中的节点

分析

交换链表中的两个点，实际上涉及到四个点

即，我们要交换 AB 两个节点，实际上涉及到前、A、B、后四个节点，其中要求改的为前、A、B 三个节点。
而 AB 这两个节点其实也可以通过最前面那个节点的 next 指针访问到，于是思路就有了，用 while 循环，一次循环交换两个节点，交换完成后往后走两个节点，如果后面不足两个节点，就跳出来，这就是大概的思路。
在循环中设置下一此交换的头结点的时候，很容易搞错，因为节点的指针已经更换了，一个万无一失的办法就是从当前循环的 nowNode 通过 next 来访问 nowNode.next.next。

解题

public ListNode swapPairs(ListNode head) {
    ListNode dummyHead = new ListNode(-1,head);
    ListNode nowNode = dummyHead;
    while(true){
        ListNode nextNode = nowNode.next;
        if(nextNode==null){
            break;
        }
        ListNode nextNextNode = nextNode.next;
        if(nextNextNode==null){
            break;
        }
        // 交换之前，先把nextNextNode的下一个节点找到
        ListNode finalNode = nextNextNode.next;
        // 开始交换
        nowNode.next = nextNextNode;
        nextNextNode.next = nextNode;
        nextNode.next = finalNode;
        // 更新当前节点，这个地方很容易搞错，因为节点的位置已经更换了，
        // 一个万无一失的办法就是从 nowNode 通过 next 来访问。
        nowNode = nowNode.next.next;
    }
    return dummyHead.next;
}

更高级的方法，用递归，递归的思路先交换后面的，再交换前面的，交换完后面的，其结果再参与到前面的交换中。非常短小精妙，当然写起来也更容易写错。哈哈哈

private static ListNode swapPairs1(ListNode head) {  
    if (head == null || head.next == null) {  
        return head;  
    }  
    // 调用swapPairs1的返回结果恰恰跟返回newHead连接上了，简短，精妙  
    ListNode nextPair = swapPairs1(head.next.next);  
    head.next.next = head;  
    head.next = nextPair;  
    return head.next;  
}

24. 两两交换链表中的节点

分析

解题

相关题